\section{Solution Technique}
\label{sec:technique}

Figure 3 presents the algorithm to solve the over-subscription
planning problem described above.  Line 1 initializes the set O,
representing the set of goals that have not yet been submitted for
insertion into the partial plan s. It also initializes an empty tour
for t. Line 2 computes an initial solution using refinement search
\cite{corman}. No goals are submitted. The solution is simply a
refinement of the initial conditions, which are presented as a partial
plan. This preliminary solution will have no utility since it has no
goals. If no consistent and complete solution exists for the initial
conditions absent additional goals, then no solution exists and you
return as in line 3. As we will see subsequently, the Cost Map M, and
Cost Bound B, can be applied as constraints and heuristics in the
Refine algorithm. Line 4 begins a process of iteration, incrementally
extending the solution one goal at a time. First, a new goal, g, is
selected via GoalSelect. If there are no more goals, the current
solution is returned. Goal selection operates as a goal-ordering
heuristic to accomplish an efficient tour of locations. It also
behaves as a filter, since goals may be excluded to arrive at a
feasible solution. The new goal is removed monotonically from O (line
6). If goal g cannot be inserted into s it is excluded from further
consideration. We then solve for the new goal, g, given the current
partial plan s. Goals are rejectable, that is they can be legally
omitted from the plan. If the goal is rejected, its score will not be
included in the calculation of utility, and it will not impact any
costs either. It is worth emphasizing that the algorithm does not
backtrack at this point to re-consider goals already inserted. Rather,
it will move on to another goal. We will now look at components of
this algorithm in more detail.

\subsection{Construction of a Cost Map}
\label{sec:tech:cost}

Before executing OSSolve we compute the cost map, M. The cost map
provides cost estimates for edges in the orienteering graph; the
construction of M is application dependent. In our application, we
define a distance graph of nodes and edges to define the traversable
links. Edge weights are the Euclidean distance between nodes of an
edge. The cost map is then constructed for all pairs of goals using
Dijkstra’s algorithm \cite{corman} over the distance graph.

\subsection{Goal Selection with Local Search}
\label{sec:tech:local}

Figure 4 describes a variant of steepest-ascent hill-climbing
\cite{michalewicz} to solve the orienteering-problem. The parameter of
particular interest is the tour, t. where , This is represented as a
sequence of goals. The algorithm begins by computing R, the set of
rejected goals; this can be a simple lookup. R is used to test if a
goal that was considered part of the tour was in fact rejected rather
than inserted. That may occur where additional constraints in the full
problem description necessitate removal of such goals for completion
of a mission (e.g when adverse currents result in longer traversal
times). If so, the tour is to include only the goals that have been
inserted into the plan successfully. The central element of the local
search is contained within the loop. In order to allow escape from a
local maximum, a new solution that is no worse than the current
solution will dominate. In order to avoid thrashing around a plateau
in the solution space, a limit is placed on the number of promotions
that can occur with no improvement in the score.  The relational
operators used to compare tours directly exploit M and B. For each
tour considered, the cost is estimated by summing the shortest path
costs along the tour, starting from the beginning. The cost map can
provide O(1) access times for pair-wise costs if stored in an
adjacency matrix, making cost evaluation linear in the length of the
tour. Utility is computed according to the sum over the goals in the
tour: where K and P are integer constants and p(i) is the priority of
the ith goal in the tour. The selection of K and P are specified to
ensure a lexicographic ordering of goals (e.g. a goal with priority of
1 dominates any combination of goals with priority > 1). In our tests,
K is 10 and P is 5. Our evaluation policy reflects a preference for
feasible plans first, and maximizing utility second. Feasibility is
evaluated by comparing the tour cost to B. Feasible candidates
dominate infeasible candidates. Higher utility dominates when both
candidates are feasible. Lower cost dominates when both candidates are
infeasible. Otherwise a simple comparison of utility/cost is
used. Otherwise a simple comparison of utility/cost is used.

The bestNeighbor function returns a candidate solution in the
neighborhood of the current best tour with the best score – hence a
steepest-ascent hill-climb. A neighbor is a tour that is obtained by
applying exactly one of the following operators to the current tour:

\begin{enumerate}

\item \emph{insert} – insert one of the goals in O, in one of the
  positions in t. Removes a goal from O if promoted.

\item \emph{swap} – swap 2 goals in t.

\item \emph{remove} – remove one of the goals in t. Inserts a goal in O
  if promoted.

\end{enumerate}

The scoring of a candidate can use the same comparator used in
GoalSelect. There are O(N2) neighbors to consider in the worst case,
where N is the number of goals. Not all operators make sense all the
time. . For example, there is no insertion possible if all goals are
already present in the tour, or if the current tour is infeasible.

\subsection{Refinement Search}

Recall that the orienteering problem is only an abstraction of the
underlying over-subscription problem. In practice, there can be
substantial additional detail in the plan that must be filled in. For
example, a detailed path may be traversed to move from one location of
scientific interest to another. Furthermore, a range of science
observations may be required to accomplish the science goal. All these
refinements can impact available time and energy on the AUV. For this
detailed planning we use refinement search.  Refinement search is the
process of solving a planning problem by searching the space of
partial plans \cite{rao95}.  The final plan is a monotonic refinement
of the initial partial plan. Our work uses \eu \cite{frank2003} to
implement this algorithm an open-source library for constraint-based
temporal planning. We exploit the Cost Map in two ways within the \eu
framework:

\begin{enumerate}

\item Detailed path planning can exploit the cost map to guide path
  selection decisions. It can prune infeasible path choices and select
  choices that minimize the distance to the end goal.

\item Cost information can be used, in conjunction with other elements
  of the model (e.g. speed) to propagate temporal bounds on actions in
  the plan, allowing further pruning of the search space.

\end{enumerate}